// nc45 实现二叉树先序，中序和后序遍历
// https://www.nowcoder.com/practice/a9fec6c46a684ad5a3abd4e365a9d362 输入
//{1,2,3} 返回值：[[1,2,3],[2,1,3],[2,3,1]]

#include <algorithm>
#include <string>
#include <vector>
using namespace std;

struct TreeNode {
  int val;
  struct TreeNode* left;
  struct TreeNode* right;
};

class Solution {
 public:
  void preOrder(TreeNode* root, vector<int>& vNum) {
    if (root == nullptr) {
      return;
    }
    vNum.push_back(root->val);
    preOrder(root->left, vNum);
    preOrder(root->right, vNum);
  }

  void midOrder(TreeNode* root, vector<int>& vNum) {
    if (root == nullptr) {
      return;
    }
    midOrder(root->left, vNum);
    vNum.push_back(root->val);
    midOrder(root->right, vNum);
  }

  void postOrder(TreeNode* root, vector<int>& vNum) {
    if (root == nullptr) {
      return;
    }
    postOrder(root->left, vNum);
    postOrder(root->right, vNum);
    vNum.push_back(root->val);
  }

  /**
   *
   * @param root TreeNode类 the root of binary tree
   * @return int整型vector<vector<>>
   */
  vector<vector<int> > threeOrders(TreeNode* root) {
    // write code here
    // 值：[[1,2,3],[2,1,3],[2,3,1]]
    // 值：[[1,2,3],[2,1,3],[2,3,1]]
    vector<vector<int> > vvNumber;
    vector<int> vNum;
    vNum.clear();
    preOrder(root, vNum);
    vvNumber.push_back(vNum);

    vNum.clear();
    midOrder(root, vNum);
    vvNumber.push_back(vNum);

    vNum.clear();
    postOrder(root, vNum);
    vvNumber.push_back(vNum);
    return vvNumber;
  }
};
